# 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
# 你的算法时间复杂度必须是 O(log n) 级别。


class Solution:
    def searchRange(self, nums, target):
        if nums.count(target) == 0:
            return [-1, -1]
        len_nums = len(nums) - 1
        if len_nums == 0:
            return [0, 0]
        i, j, min_i, max_j = 0, len_nums, 0, len_nums
        while j - i >= 1:
            if nums[i] != target or (i != 0 and nums[i-1] == target):
                if nums[i] >= target:
                    if i != (i+min_i) // 2:
                        i = (i+min_i) // 2
                    else:
                        i -= 1
                elif nums[i] < target:
                    min_i = i
                    if (j-i) // 3 > 1:
                        i += (j-i) // 3
                    else:
                        i += 1
            if nums[j] != target or (j != len_nums and nums[j + 1] == target):
                if nums[j] <= target:
                    if j != (j+max_j) // 2:
                        j = (j+max_j) // 2
                    else:
                        j += 1
                elif nums[j] > target:
                    max_j = j
                    if (j-i) * 2 // 3 > 1:
                        j -= (j-i) * 2 // 3
                    else:
                        j -= 1
            if nums[i] == target and (i == 0 or nums[i-1] != target) and \
                            nums[j] == target and (j == len_nums or nums[j+1] != target):
                return [i, j]


a = Solution()
print(a.searchRange([1,1,1,2,4,4,4,5,5,5,5,6,7,8,8,9,9,9,9,9,9,10],9))